1. Field of the Invention
The present invention relates to the telecommunication field and more in particular to the art of correction of errors which could be originated during the transmission of signals. Still more in particular, the present invention relates to an improved erasure FEC decoder and an improved method for decoding signals.
This application is based on, and claims the benefit of, European Patent Application No. 04290408.6 filed on Feb. 13, 2004, which is incorporated by reference herein.
2. Description of the Prior Art
As it is known, the Forward Error Correction (FEC) is a technique by means of which redundancy is transmitted together with transported data, using a pre-determined algorithm. The receiving device has the capability of detecting and correcting multiple bit errors that could occur during transmission thanks to the redundancy. The signal transmitted with FEC is more “robust” thus allowing operators to build up longer distance connections without the deployment of many repeater stations.
It is known to decode a two-dimensional code by using a mono-dimensional iterative decoding along both the dimensions. This because the error correction capability increases according to the number of iterations. This decoding method is not optimal and despite a decoder can correct a large number of errors by exploiting an iterative procedure, there are some error patterns that can not be corrected by using such a procedure. This is a limit to the BER_out. For this reason, this phenomenon is commonly called “decoding BER floor”.
This “decoding BER floor” can be removed by using the information coming together from the two dimensions reaching “the code BER floor” that is intrinsic to the code itself.
Two are the main problems that have to be solved. From one side, it is necessary to find the remaining error positions. From the other side, it is necessary to calculate the values of the remaining errors.
Let's consider, for instance, a BCH two-dimensional code with a correction capability of three errors for both the directions. Let's also suppose, for example, that:                the minimum distance for horizontal codes is eight (dH=8),        the minimum distance for vertical codes is seven (dv=7), and        the number of bits that, at most, two codewords have in common (cell) is two.        
There are error configurations that, by using a monodimensional iterative decoding, are not correctable. The most common pattern of errors that can not be corrected through an iterative decoding consists in eight errors distributed in four cells. If the above-mentioned cells are arranged in a way that four errors are present in all directions, no codewords are correctable by using a mono-dimensional decoding because the error correction capability is only of three symbols (in this case, BCH code, three bits). Further critical configurations (BER floors) that are not correctable through an iterative decoding could consist in 12-18 errors distributed in nine cells et caetera.
From a European patent application filed on the same date and by the same Applicant as the present patent application, titled “improved iterative n-dimensional decoding”, a decoder for performing an iterative n-dimensional decoding of a data structure is known. A corresponding decoding method is also known from the same paper. Such a patent application is incorporated herewith as a reference. The invention disclosed in such a parallel application is based on the fact that, being the algebraic codes resolvable by a closed formula up to a fourth grade equation, for a n-dimensional code, in which each dimension is protected by an algebraic code having a grade ≦4, it is possible to use a novel decoding computing structure that use a closed form solution to calculate errors values and their positions. The novel computing structure does not need to compute all syndromes (in all dimensions) at each decoding step. According to the invention, syndromes are computed once at the beginning of the decoding step. After that, when a bit is corrected, all the syndromes affected by such a correction are updated. The basic idea of the invention disclosed in the parallel patent application is that, from the second iteration up to the nth iteration, only the syndromes with a value different from zero, or the syndromes that have been updated during the previous decoding step, are processed. In this way, the time required by each sub-iteration (from second sub-iteration on) will be progressively reduced.
The processing of the syndromes is managed by a sequencer which is provided with information about the position of remaining errors at each step of the iterative process. Whilst the iterative n-dimensional decoding of a data structure according to the parallel patent application is highly effective, the above mentioned patterns of errors can not be corrected in any case but the information about the position of errors is already known by the sequencer. This is the basic point to start the erasure alghoritm. When a similar situation arises, an erasure method should be carried out.
Erasure methods are known. Generally an erasure method allows to remove some of the above-mentioned error patterns. It is based on the fact that the decoder is able to identify all the cells in which there are errored bits. In some cases, however, false corrections are possible.
The Applicant is aware of more than one theoretical algorithms that allow to solve both the above-mentioned problems in case of two-dimensional codes. However, such methods are difficult to be implemented due to their complexity. In addition, the already existing erasure algorithms are not able to identify all the cells in case of false corrections.